package workexp.alg.question;

import org.junit.Test;

import java.util.*;

public class TwoSum {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[]{-1, -1};
        if (numbers.length < 2) {
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                res[0] = map.get(target - numbers[i]);
                res[1] = i + 1;
                return res;
            }
            map.put(numbers[i], i + 1);
        }

        return res;
    }

    public int[] twoSum2(int[] numbers, int target) {
        int[] res = new int[]{-1, -1};
        if (numbers.length < 2) {
            return res;
        }
        int i=0;
        int j=numbers.length-1;

        while(i<j){
            int m = (i+j)>>>1;
            if(numbers[i]+numbers[m]>target){
                j=m-1;
            }else if(numbers[j]+numbers[m]<target){
                i=m+1;
            }else if(numbers[i]+numbers[j]>target){
                j--;
            }else if(numbers[i]+numbers[j]<target){
                i++;
            }else{
                res[0]=i+1;
                res[1]=j+1;
                break;
            }
        }

        return res;
    }

    @Test
    public void test(){
        int[] nums = {0,0,3,4};
        int[] result = twoSum2(nums,0);
        System.out.println(Arrays.toString(result));
    }
}
